package com.dmall.sort.algorithm;

import java.util.Arrays;

/**
 * 插入归并排序算法
 * @author xiao1.wang
 * @date 2021/10/7 21:05
 */
@SuppressWarnings("all")
public class InsertionMergeSort implements Sort {

    private static final int INSERTION_THRESHOLD = 32;

    @Override
    public void sort(int[] arr) {
        if (arr.length <= 1) {
            return;
        }
        int[] temp = Arrays.copyOf(arr, arr.length);
        sort(arr, 0, arr.length - 1, temp);
    }

    private void sort(int[] arr, int l, int r, int[] temp) {
        if (r - l <= INSERTION_THRESHOLD) {
            InsertionSort.insertionSort(arr, l, r);
            return;
        }
        int mid = l + (r - l) / 2;
        sort(arr, l, mid, temp);
        sort(arr, mid + 1, r, temp);
        if (arr[mid] > arr[mid + 1]) {
            merge(arr, l, mid, r, temp);
        }
    }

    private void merge(int[] arr, int l, int mid, int r, int[] temp) {
        System.arraycopy(arr, l, temp, l, r - l + 1);
        int left = l;
        int right = mid + 1;
        int index = l;
        while (left <= mid && right <= r) {
            if (temp[left] <= temp[right]) {
                arr[index++] = temp[left++];
            } else {
                arr[index++] = temp[right++];
            }
        }
        while (left <= mid) {
            arr[index++] = temp[left++];
        }
        while (right <= r) {
            arr[index++] = temp[right++];
        }
    }

    @Override
    public String getName() {
        return "插入归并排序";
    }
}
